Internet protocol (IP) traffic follows rules established by routing protocols. Shortest path based protocols, such as Open Shortest Path First (OSPF), direct traffic based on arc weights assigned by the network operator. Each router computes shortest paths and creates destination tables used for routing flow on the shortest paths. It is also the role of the routing protocol to specify how the network should react to changes in the network topology, such as changes in arc weights. However, arc weights may change for various reasons, e.g., failure of an arc, maintenance being performed on one or more links within an arc, congestion, new weight assignment from the network operator, and the like. When an arc weight is changed on an arc (e.g., increased or decreased), a dynamic shortest path algorithm is triggered, e.g., within each node, to update the shortest paths within the affected network taking into account the change in the arc weight. However, running the dynamic shortest path algorithm is a time consuming method, i.e., a computationally expensive method.
Therefore, a need exists for a method and apparatus for accelerating the update of a shortest path graph for networks such as packet networks.